1. Field of Invention
This invention relates to the identification and retrieval of digital data by a computing device.
2. Prior Art
A method for the discovery of a set of digital data (SDD), such as images, videos, and the like, that are organized for point-wise presentation in two-dimensions, that are similar to a target SDD is invented here. Formulae for the areas of the sheets swept out by the data are used as signatures that characterize equivalence classes of SDDs with the same or numerically close data. The method leverages these “equivalence signatures” to find SDDs that are similar to target SDDs and, separately and alternatively, find SDDs that are dissimilar from the target SDDs.
The definition of “similarity”, and thus the features and method used to compute it, is idiosyncratic to the retrieval application [O'Connor]. In the case of image retrieval [Gonzalez], methods using entropy, moments, etc. as signatures, have been invented [U.S. Pat. Nos. 5,933,823; 5,442,716]. Another invention [U.S. Pat. No. 7,246,314], uses closeness to a Gaussian model as a similarity measure for identifying similar videos.
The cost of implementing these methods is typically proportional to the product of the number of SDDs in the database with the cost of computing the distance between the target SDD and another SDD. The latter often [Raghavan] involves the computation of the projection angle between two vectors that represent the features (e.g., histogram of the text elements) of the SDDs. For large databases, this process can be both resource and time expensive. A two step method is required wherein, during the retrieval phase, definitely dissimilar SDDs are first weeded out thereby significantly reducing the number of candidates for similarity. This first step should be computationally inexpensive thus significantly reducing the resource requirements and latency in computing the results of the second step, the application of traditional features.
Intuitively, if two SDDs are similar, then they should be locally deformable into each other. For example, if two images are rescalings and/or rotations of each other, then the images are similar. This invention leverages results from String Theory to address this problem. In particular, we appeal to field theory representations for the areas of sheets swept out by the SDD when stepping through the presentation space. By construction, these volumes are invariant under reparameterizations of the presentation space and thus characterize equivalence classes of area preserving maps between the presentation and data spaces.
We interpret each SDD as a sampling of maps from an two-dimensional space, N; with coordinates, (θ1, θ2) to an m-dimensional space, M, with coordinates σA (θ1, θ2) or σA(θ) for short, for A=1, . . . , m and seek volume preserving equivalence classes of such maps. The cases where m≧n are considered. We label the lengths of the presentation space dimensions as L(1) and L(2) or width and height.
Let the raw data, {tilde over (σ)}A(θ), of each SDD be organized into m data planes, e.g., three YUV color planes of images, for presentation and let each plane have a maximum and minimum value for the data in that plane, {tilde over (σ)}maxA and {tilde over (σ)}minA, respectively. The maximum and minimum values of each of the two planes are used to normalize their data to new minimum and maximum values, σmaxA and σminA respectively, through the expressions:
                                          σ            A                    ⁡                      (            θ            )                          =                                                                              σ                  max                  A                                -                                  σ                  min                  A                                                                                                  σ                    ~                                    max                  A                                -                                                      σ                    ~                                    min                  A                                                      ⁡                          [                                                                                          σ                      ~                                        A                                    ⁡                                      (                    θ                    )                                                  -                                                      σ                    ~                                    max                  A                                            ]                                +                      σ            min            A                                              Eqn        .                                  ⁢        1            
Additional normalizations of the SDD, such as scaling to a fixed width and height and the like, may also be performed.
If objects have been segmented from the SDD then the data for these objects are themselves SDDs. We henceforth refer to each segmented portion as a “SDD section” with its own map, σ.
For SDD sections for two-dimensional presentation where there are at least two planes of data, such as images or video frames, the expression for the equivalence signature resolves to the area of the sheet represented by the data [Kaku], namely
                              ξ          ⁡                      [            σ            ]                          ≡                              ∫            0                          L              1                                ⁢                                    ∫              0                              L                2                                      ⁢                                                  ⁢                                          ⅆ                                  θ                  1                                            ⁢                                                          ⁢                              ⅆ                                  θ                  2                                            ⁢                                                                                          (                                                                        ∑                                                      A                            =                            1                                                    m                                                ⁢                                                                                                            ∂                                                              σ                                A                                                                                                                    ∂                                                              θ                                1                                                                                                              ⁢                                                                                    ∂                                                              σ                                A                                                                                                                    ∂                                                              θ                                1                                                                                                                                                        )                                        ⁢                                          (                                                                        ∑                                                      B                            =                            1                                                    m                                                ⁢                                                                                                            ∂                                                              σ                                B                                                                                                                    ∂                                                              θ                                2                                                                                                              ⁢                                                                                    ∂                                                              σ                                B                                                                                                                    ∂                                                              θ                                2                                                                                                                                                        )                                                        -                                                            (                                                                        ∑                                                      A                            =                            1                                                    m                                                ⁢                                                                                                            ∂                                                              σ                                A                                                                                                                    ∂                                                              θ                                1                                                                                                              ⁢                                                                                    ∂                                                              σ                                A                                                                                                                    ∂                                                              θ                                2                                                                                                                                                        )                                        2                                                                                                          Eqn        .                                  ⁢        2            
SDD sections that have the same value for the equivalence signature will belong to the same equivalence classes under:                reparametrizations of the presentation space (e.g., warping of the image)        rotations of the presentation space (e.g., rotating an image from landscape to portrait)        resealing of the presentation space (e.g., changing the sizes of images)        offsets in the data values (e.g., change in the brightness of images)        replacing the data values with their mirrored values        global, orthogonal rotations of the planes into each otherseparately and collectively. Proofs of these symmetries are recounted in works such as Ref. [Kaku].        
Consider two SDD sections, σ′A (θ) and σA(θ) such that at each point, the difference between the values of the maps is εA (θ),εA(θ)=σ′A(θ)−σA(θ)  Eqn. 3
For the two SDD sections to be similar we take εA (θ) to be small compared with σA(θ) so that terms of order ε2(θ) can be neglected. With this as a quantitative measure of similarity, we can assign bounds on the differences of the equivalence signatures via the functional difference:Δξ[σ;ε]≡ξ[σ+ε]−ξ[σ]  Eqn. 4
As εA (θ) is small, to a first approximation, Δξ[σ; ε] is a linear functional of εA. We will exploit this henceforth.
For example, suppose we are interested in finding images the data values of whose color planes differ by no more than p percent at each pixel, then εA (θ)=pσA(θ) are used in the computation of Δξ[σ; ε]. Retrieval of similarity candidates proceeds by finding those images with values of ξ[σ], denoted as ξ[σsimilar], for which the following inequalities hold:|ξ[σtarget]−ξ[σsimilar]|≦Δξ[σtarget;ε]  Eqn. 5
As an example for the reduction factor for the number of CPU cycles and other resources required in finding similar sections of SDDs in a corpus, assume for simplicity that the equivalences signatures of the SDD sections in the corpus are uniformly distributed in [ξmax, ξmin]. If for a target SDD section, the choice of similarity lead to Δξ[σ; ε], the reduction in the number of secondary features to be compared is
                              f          r                =                              (                                          2                ⁢                                                                  ⁢                Δ                ⁢                                                                  ⁢                                  ξ                  ⁡                                      [                                          σ                      ;                      ɛ                                        ]                                                              +              1                        )                                (                                          ξ                max                            -                              ξ                min                            +              1                        )                                              Eqn        .                                  ⁢        6            
In state of the art information retrieval methodologies, the feature vector which is used for each SDD section would have to be compared to all Nc feature vectors computed for the SDD sections in the corpus. Upon employing the method invented here as a precursor to the feature vector comparison, the number of feature vectors to be compared would be reduced to f, Nc.